/*
Problem Description
Some of the secret doors contain a very interesting word puzzle. The team
of archaeologists has to solve it to open that doors. Because there is no
other way to open the doors, the puzzle is very important for us.
There is a large number of magnetic plates on every door. Every plate has
one word written on it. The plates must be arranged into a sequence in such
a way that every word begins with the same letter as the previous word
ends. For example, the word acm can be followed by the word motorola.
Your task is to write a computer program that will read the list of words and
determine whether it is possible to arrange all of the plates in a sequence
(according to the given rule) and consequently to open the door.
Input
The input consists of T test cases. The number of them (T) is given on the
first line of the input file. Each test case begins with a line containing a
single integer number Nthat indicates the number of plates (1 <= N <=
100000). Then exactly Nlines follow, each containing a single word. Each
word contains at least two and at most 1000 lowercase characters, that
means only letters 'a' through 'z' will appear in the word. The same word
may appear several times in the list.
Output
Your program has to determine whether it is possible to arrange all the
plates in a sequence such that the first letter of each word is equal to the last
letter of the previous word. All the plates from the list must be used, each
exactly once. The words mentioned several times must be used that number
1
of times.
If there exists such an ordering of plates, your program should print the
sentence "Ordering is possible.". Otherwise, output the sentence "The door
cannot be opened.".
Sample Input
3
2
acm
ibm
3
acm
malform
mouse
2
ok
ok
Sample Output
The door cannot be opened.
Ordering is possible.
The door cannot be opened.

 */
package com.yuan.algorithms.training201608;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;

/**
 * @author YouYuan
 * @contact 1265161633@qq.com
 * @date 2016年8月16日 下午12:35:59
 * @descript 题目大意：给你一些英文单词，判断所有单词能不能连成一串，类似成语接龙的意思。
 * 			但是如果有多个重复的单词时，也必须满足这样的条件才能算YES。否则都是不可能的情况。
 *			解题思路：欧拉路。
 *          1.并查集判断连通
			2.将每个单词取出首字母和尾字母，转换为一条边，然后加入对应的
			连通分量中。如果这个字母出现过，visit数组标记为true。同时起点出度加1，终点入度加1.
			3.判断：
			1）这个图必须是连通的，即根结点只有一个。如果不是，直接结束本次算法。
			2）如果这个图是连通的，判断每个结点的入度和出度情况。
			如果这个图是欧拉路，则每个顶点的出度等于入度。即out[i] = in[i]
			如果这个图是半欧拉图，则起点的出度比入度大1，终点的入度比出
			度大1.其余顶点的出度等于入度。
			如果满足上述条件，就可以将所有单词链接起来，否则不能。
 */
public class C_单词回路_hdu1116 {
	//创建缓冲输入流和输入流，加速输入输出
	static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

	public static int nextInt() throws IOException {
		in.nextToken();
		return (int) in.nval;
	}

	public static String next() throws IOException {
		in.nextToken();
		return in.sval;
	}

	
	static final int size = 27;//一共26个英文字母，下标从1开始
	static int[] pre = new int[size];//用于并查集
	static int[] inDegree = new int[size];//表示每个单词的尾部字母的入度，默认是0
	static int[] outDegree = new int[size];//表示每个单词的头部字母的出度，默认是0
	static boolean[] visited = new boolean[size];//字母是否出现，默认是false
	static int inNum, outNum;//出现的所有的字母,“入度减出度为1”和“出度减入度为1”的个数
	static int root;//根节点个数
	static boolean flag; //判断出现的所有的字母的出度和入度之差是否是0或1，如果不是，那肯定不满足题意,还有判断root是否大于1，大于1的话，肯定不满足  
	static int start, last;//开始字母和结束字母
	
	public static void main(String[] args) throws IOException {
		//while(in.hasNext()) {//这道题不用写这句话，坑死了！
			int t = nextInt();
			while (--t >= 0) {
				initialize();//初始化数据
				int n = nextInt();
				for (int j = 0; j < n; j++) {
					String word = next();
					start = word.charAt(0) - 'a' + 1;
					last = word.charAt(word.length()-1) - 'a' + 1;
					visited[start] = true;
					visited[last] = true;
					outDegree[start]++;
					inDegree[last]++;
					union(start, last);
				}
				judge();
				if ((flag && inNum == 0 && outNum == 0) || (flag && inNum == 1 && outNum == 1)) {
					System.out.println("Ordering is possible.");
				} else {
					System.out.println("The door cannot be opened.");
				}
			}
		//}
	}
	
	private static void judge() {
		for (int j = 1; j < size; j++) {
			if (visited[j]) {
				if (pre[j] == j) {
					root++;
				}
				if (outDegree[j] != inDegree[j]) {
					if (outDegree[j] - inDegree[j] == 1) {
						outNum++;
					} else if (inDegree[j] - outDegree[j] == 1) {
						inNum++;
					} else {
						flag = false;
						return;
					}
				}
			}
			if (root > 1) {
				flag = false;
				return;
			}
		}
	}

	private static void initialize() {
		for (int j = 1; j < pre.length; j++) {
			pre[j] = j;//初始化并查集
		}
		Arrays.fill(inDegree, 0);
		Arrays.fill(outDegree, 0);
		Arrays.fill(visited, false);
		inNum = outNum = root = 0;
		flag = true;
	}

	public static int find(int x) {
		return (x != pre[x]) ? find(pre[x]) : x;
	}

	public static void union(int x, int y) {
		int root_x = find(x);
		int root_y = find(y);
		if (root_x != root_y) {
			pre[root_x] = root_y;
		}
	}
	
}
